package LC;

/**
 * https://leetcode.com/problems/implement-strstr/description/
 * Implement strStr().
 * Returns the index of the first occurrence of needle in haystack,
 * or -1 if needle is not part of haystack.
 */
public class LC_028_ImplementstrStr_KMP {
    public static void main(String[] args) {
        String s = "12345";
        String m = "4";
        int idx1 = Solution_1.strStr(s, m);
        int idx2 = Solution_2.strStr(s, m);
        System.out.println(idx1);
        System.out.println(idx2);
    }

    static class Solution_1 {
        static int strStr(String haystack, String needle) {
            return haystack.indexOf(needle);
        }
    }

    static class Solution_2 {
        static int strStr(String haystack, String needle) {
            if ("".equals(needle))
                return 0;
            if (haystack == null || needle == null || needle.length() < 1 || haystack.length() < needle.length()) {
                return -1;
            }
            char[] ss = haystack.toCharArray();
            char[] ms = needle.toCharArray();
            int si = 0;
            int mi = 0;
            int[] next = getNextArray(ms);
            while (si < ss.length && mi < ms.length) {
                if (ss[si] == ms[mi]) {
                    si++;
                    mi++;
                } else if (next[mi] == -1) {
                    si++;
                } else {
                    mi = next[mi];
                }
            }
            return mi == ms.length ? si - mi : -1;
        }

        static int[] getNextArray(char[] ms) {
            if (ms.length == 1) {
                return new int[]{-1};
            }
            int[] next = new int[ms.length];
            next[0] = -1;
            next[1] = 0;
            int pos = 2;
            int cn = 0;
            while (pos < next.length) {
                if (ms[pos - 1] == ms[cn]) {
                    next[pos++] = ++cn;
                } else if (cn > 0) {
                    cn = next[cn];
                } else {
                    next[pos++] = 0;
                }
            }
            return next;
        }
    }
}
